package puzzle.projecteuler.p200;


public class Problem117 {

	/**
	 * 对比Problem116
	 * @param args
	 */
	public static void main(String[] args) {

		System.out.println(c(5));
		System.out.println(c(50));
	}

	/**
	 * c(n) = c(n-1) + c(n-2) + c(n-3) + c(n-4)
	 * c(n-1):第一格空着
	 * c(n-2) + c(n-3) + c(n-4): 第一格不空的放置方法数
	 * @param n
	 * @return
	 */
	public static long c(int n) {

		long[] count = new long[n+1];
		for (int i = 0; i < count.length; i ++) {
			if (i == 0 || i == 1) {
				count[i] = 1;
			} else if (i == 2) {
				count[i] = 2;
			} else if (i == 3) {
				count[i] = 4;
			} else if (i == 4) {
				count[i] = 8;
			} else {
				count[i] = count[i-1]+count[i-2]+count[i-3]+count[i-4];
			}
		}
		return count[n];
	}
}
